/*
 * Regular Expression Matching
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") > false
isMatch("aa","aa") > true
isMatch("aaa","aa") > false
isMatch("aa", "a*") > true
isMatch("aa", ".*") > true
isMatch("ab", ".*") > true
isMatch("aab", "c*a*b") > true
 */
package com.xinpan.exercise;


public class RegularExpressionMatching {
    public boolean isMatch(String s, String p) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(p.length() == 0)
            return s.length() == 0;
        
        
        if(p.length() == 1 || p.charAt(1) != '*')
        {
            if(s.length() == 0)
                return false;
            if(p.charAt(0) == '.' || p.charAt(0) == s.charAt(0))
                return isMatch(s.substring(1, s.length()),
                                p.substring(1, p.length()));
            else 
                return false;
        }
        
        if(isMatch(s.substring(0, s.length()),
                            p.substring(2, p.length())))
            return true;
        
        for(int i = 0; i < s.length(); i++)
        {
            if(p.charAt(0) == '.')
            {
                if(isMatch(s.substring(i+1, s.length()), p.substring(2, p.length())))
                    return true;
            }
            else if(p.charAt(0) == s.charAt(i))
            {
                if(isMatch(s.substring(i+1, s.length()), p.substring(2, p.length())))
                    return true;
            }
            else
                return false;
        }
        return false;
    }
    
    public static void main(String[] args)
    {
    	RegularExpressionMatching rem = new RegularExpressionMatching();
    	System.out.println(rem.isMatch("aa", "a*"));
    }
}
